{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# On-Site Question 3 - SOLUTION\n",
    "\n",
    "## Problem\n",
    "\n",
    "**Given two rectangles, determine if they overlap. The rectangles are defined as a Dictionary, for example:**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "r1 = {\n",
    "    \n",
    "         # x and y coordinates of the bottom-left corner of the rectangle\n",
    "         'x': 2 , 'y': 4,\n",
    "         \n",
    "         # Width and Height of rectangle\n",
    "         'w':5,'h':12}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "** If the rectangles do overlap, return the dictionary which describes the overlapping section**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Requirements\n",
    "\n",
    "** Make sure the dictionary you output is in the same form as the input.**\n",
    "\n",
    "** Feel free to use an IDE for the code, but make sure you use paper/pencil or whiteboard to draw out your plan and logic**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Solution\n",
    "\n",
    "This is a problem where it helps a lot to draw out your thinking. There are a few things we will need to think about:\n",
    "\n",
    "* How can we determine an intersection?\n",
    "* What if a rectangle is fully inside another rectangle?\n",
    "* What if there is no intersection, but the rectangles share an edge?\n",
    "\n",
    "The key to solving this problem is to *break it up in to sub-problems*. We can split up the problem into an x-axis problem and a y-axis problem. \n",
    "\n",
    "We will create a function that can detect overlap in 1 dimension. Then we will split the rectangles into x and width, and y and height components. We can then determine that if there is overlap on both dimensions, then the rectangles themselves intersect!\n",
    "\n",
    "In order to understand the **calc_overlap** function, draw out two flat lines and follow along with the function and notice how it detects an overlap!\n",
    "\n",
    "Let's begin by creating a general function to detect overlap in a single dimension:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def calc_overlap(coor1,dim1,coor2,dim2):\n",
    "    \"\"\"\n",
    "    Takes in 2 coordinates and their length in that dimension\n",
    "    \"\"\"\n",
    "    \n",
    "    # Find greater of the two coordinates\n",
    "    # (this is either the point to the most right\n",
    "    #  or the higher point, depending on the dimension)\n",
    "    \n",
    "    # The greater point would be the start of the overlap\n",
    "    greater = max(coor1,coor2)\n",
    "    \n",
    "    # The lower point is the end of the overlap\n",
    "    lower = min(coor1+dim1,coor2+dim2)\n",
    "    \n",
    "    # Return a tuple of Nones if there is no overlap\n",
    "    \n",
    "    if greater >= lower:\n",
    "        return (None,None)\n",
    "    \n",
    "    # Otherwise, get the overlap length\n",
    "    overlap = lower-greater\n",
    "    \n",
    "    return (greater,overlap)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now let's use this function to detect if the rectangles overlap!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def calc_rect_overlap(r1,r2):\n",
    "    \n",
    "    \n",
    "    x_overlap, w_overlap = calc_overlap(r1['x'],r1['w'],r2['x'],r2['w'])\n",
    "    \n",
    "    y_overlap, h_overlap = calc_overlap(r1['y'],r1['h'],r2['y'],r2['h'])\n",
    "    \n",
    "    # If either returned None tuples, then there is no overlap!\n",
    "    if not w_overlap or not h_overlap:\n",
    "        print 'There was no overlap!'\n",
    "        return None\n",
    "    \n",
    "    # Otherwise return the dictionary format of the overlapping rectangle\n",
    "    return { 'x':x_overlap,'y': y_overlap,'w':w_overlap,'h':h_overlap}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Our solution is O(1) for both time and space! Let's see it in action:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'h': 11, 'w': 5, 'x': 2, 'y': 5}"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "r1 = {'x': 2 , 'y': 4,'w':5,'h':12}\n",
    "r2 = {'x': 1 , 'y': 5,'w':7,'h':14}\n",
    "calc_rect_overlap(r1,r2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Make sure to review the answer and practice writing it out by hand!\n",
    "# Good Job!"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.11"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}
